package main

import (
	"fmt"
)

//二分查找:148ms 40%，8.4MB 72%
func twoSum(nums []int, target int) []int {
	for i := 0; i < len(nums)-1; i++ {
		t := target - nums[i]
		if find(nums[i+1:], t) {
			return []int{nums[i], t}
		}
	}
	return nil
}

func find(nums []int, t int) bool {
	i, j := 0, len(nums)-1
	for i <= j {
		m := (i + j) / 2
		if nums[m] == t {
			return true
		} else if nums[m] > t {
			j = m - 1
		} else {
			i = m + 1
		}
	}
	return false
}

//双指针:132ms 95%,8.4MB 72%
func twoSum1(nums []int, target int) []int {
	i, j := 0, len(nums)-1
	for i < j {
		if nums[i]+nums[j] == target {
			return []int{nums[i], nums[j]}
		} else if nums[i]+nums[j] < target {
			i++
		} else {
			j--
		}
	}
	return nil
}

func main() {
	fmt.Println(twoSum([]int{2, 7, 11, 15}, 9))
	fmt.Println(twoSum1([]int{2, 7, 11, 15}, 9))
}
